import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;


public class Sort {
    //时间复杂度：O（N^2）
    //      最坏的情况下：逆序的
    //      最好的情况下：顺序的，如果数据越有序，直接插入排序越快
    //空间复杂度：O(1)
    //稳定性：稳定的排序
    //本身如果是稳定的排序，那么可以实现为不稳定的
    //但是如果是一个排序本身就是不稳定的能实现稳定的排序吗？答案是不稳定
    public static void insertSort(int[]array){
        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
//希尔排序是不稳定的
// 时间复杂度是n^1.3--n^1.5
// 空间复杂度是：O（1）
    public static void shellSort(int[]array){
        int gap=array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }
    }
    private  static void shell(int[]array,int gap) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    array[j + gap] = tmp;
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    //直接选择排序
    //时间复杂度：ON^2
    //空间复杂度：O1
    //不稳定

    //两个数字交换的函数
    private static void swap(int[]array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public  void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            int mindIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[mindIndex]){
                    mindIndex=j;
                }
            }
            swap(array,i,mindIndex);
        }
    }
    public  static  void selectSort2(int[]array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for(int j=left+1;j<=right;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
                if(array[j]>array[maxIndex]){
                    maxIndex=j;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    //堆排序
    //时间复杂度：o(n*logN)
    //空间复杂度：o(1)
    //稳定性：
    public static  void heapSort(int[]array){
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }

    }
    private static void createHeap(int[]array){
        //创建一个大根堆
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array, int parent, int length) {
        int child=2*parent+1;
        while (child < length) {
            if(child+1<length&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    //冒泡排序
    //时间复杂度
    //空间复杂度
    public static void bubbleSort(int []array){
        for(int i=0;i<array.length-1;i++){
            boolean flg=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

    //快速排序

    public static void quickSort(int[]array){
        //quick(array,0,array.length-1);
        //使用非递归的方法来进行排序--》运用栈来实现
        quickNor(array,0,array.length-1);
    }
    //非递归的方法
    //用栈来实现
    public  static void quickNor(int[] array, int start, int end){

        Deque<Integer> stact=new ArrayDeque<>();
        int prvot=partition(array,start,end);
        if(prvot>start+1){
            stact.push(start);
            stact.push(prvot-1);
        }
        if(prvot<end-1){
            stact.push(prvot+1);
            stact.push(end);
        }
        while (!stact.isEmpty()){
            end=stact.pop();
            start= stact.pop();
            prvot=partition(array,start,end);
            if(prvot>start+1){
                stact.push(start);
                stact.push(prvot-1);
            }
            if(prvot<end-1){
                stact.push(prvot+1);
                stact.push(end);
            }
        }
    }

    private static void quick(int[] array, int start, int end) {
        if(start>=end){
            return;
        }
        if(end-start+1<=10){
            insertSortRange(array,start,end);
        }
        int midIndex=getMiddleNum(array,start,end);
        swap(array,start,midIndex);
        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private static void insertSortRange(int[] array, int start, int end) {
        for(int i=start+1;i<=end ;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    private static int getMiddleNum(int[] array, int left, int right) {
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }

    private static int partitionhoare(int[]array,int left,int right){
        int tmp=array[left];
        int tmpleft=left;
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            while(left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpleft);
        return left;
    }
    //挖坑法
    private static int partition(int[]array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
       array[left]=tmp;
        return left;
    }
    //前后指针法
    private static int partition1(int[]array,int left,int right){
        int prev=left;
        int cur=left+1;
        while (cur<=right){
            if(array[cur]<array[left]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }




    //归并排序
    public  static  void mergeSort(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }
    private static void mergeSortTmp(int[]array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //走到这里全部分解完毕
        //合并
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int tmp[]=new int[right-left+1];
        int k=0;
        int s1=left;
        //int e1=mid;
        int s2=mid+1;
        //int e2=right;
        while(s1<=mid&&s2<=right){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else {
                tmp[k++]=array[s2++];
            }
        }
        while(s1<=mid){
            tmp[k++]=array[s1++];
        }
        while(s2<=right){
            tmp[k++]=array[s2++];
        }
        //可以保证tmp数组 是有序的
        for(int i=0;i<k;i++){
            array[i+left]=tmp[i];
        }
    }

    //归并排序的非递归实现
    public  static  void mergeSortNor(int[]array){
        int gap=1;
        while(gap<array.length){
            for(int i=0;i<array.length;i=i+gap*2){
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }

    //计数排序
    //适合在规定的范围为内进行排序
    public static void countSort(int[]array){
        //找最大值和最小值来确定数组的大小
        int maxVal=array[0];
        int minVal=array[0];
        for(int i=0;i<array.length;i++){
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
        }
        int len=maxVal-minVal+1;
        int[]count=new int[len];
        //2遍历原来数组array 把元素放到对应的计数数组当中进行计数
        for(int i=0;i<array.length;i++){
            int index=array[i];
            count[index-minVal]++;
        }
        //依次遍历计数数组
        int index=0;
        for(int i=0;i<count.length;i++){
            while(count[i]!=0){
                array[index]=i+minVal;
                index++;
                count[i]--;
            }
        }
    }


}
